package cn.icatw.leetcode.editor.cn;
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
//
//
//
// 示例 1:
//
//
//
//
// 输入：heights = [2,1,5,6,2,3]
// 输出：10
// 解释：最大的矩形为图中红色区域，面积为 10
//
//
// 示例 2：
//
//
//
//
// 输入： heights = [2,4]
// 输出： 4
//
//
//
// 提示：
//
//
// 1 <= heights.length <=10⁵
// 0 <= heights[i] <= 10⁴
//
//
// Related Topics 栈 数组 单调栈 👍 2776 👎 0


import java.util.Stack;

// Java：柱状图中最大的矩形
public class T84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new T84_LargestRectangleInHistogram().new Solution();
        // TO TEST
    }

    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack<Integer> stack = new Stack<>();
            int maxArea = 0;
            int n = heights.length;
            for (int i = 0; i < n; i++) {
                //     当前柱子高度小于栈顶柱子高度，栈顶柱子出栈，计算面积
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    int height = heights[stack.pop()];
                    int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                    maxArea = Math.max(maxArea, height * width);
                }
                stack.push(i);
            }
            //     栈中剩余柱子，计算面积
            while (!stack.isEmpty()) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? n : n - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            return maxArea;
        }
    }
// leetcode submit region end(Prohibit modification and deletion)

}
